package com.leetcode.algorithm.y22.m07.w4;

/**
 * 1376. 通知所有员工所需的时间
 * 
 * https://leetcode.cn/problems/time-needed-to-inform-all-employees/
 * 
 * @author jie.deng
 *
 */
class Question1376Solution01 {

	public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
		int[] timeArr = new int[n];
		int maxTime = 0;
		for (int i = 0; i < n; i++) {
			if (timeArr[i] == 0) {
				timeArr[i] = getInformTime(i, headID, manager, informTime, timeArr);
			}
			maxTime = Math.max(maxTime, timeArr[i]);
		}
		return maxTime;
	}

	private int getInformTime(int id, int headID, int[] manager, int[] informTime, int[] timeArr) {
		if (timeArr[id] > 0) {
			return timeArr[id];
		}
		if (headID == id) {
			return informTime[id];
		}
		int managerTime = getInformTime(manager[id], headID, manager, informTime, timeArr);
		timeArr[manager[id]] = managerTime;
		return managerTime + informTime[id];
	}

}